/* 
 * File:   main.cpp
 * Author: trunghpb
 *
 * Created on March 21, 2010, 3:11 PM

  ĐỀ SỐ 20

	Cho đồ thị vô hướng liên thông có trọng số G = <V,E> trong file dothi.in được biểu diễn dưới dạng danh sách cạnh theo khuôn dạng sau:
•	Dòng đầu tiên ghi lại số tự nhiên N, M tương ứng với số đỉnh và số cạnh của đồ thị.
•	M dòng kế tiếp mỗi dòng ghi lại ba số i, j, w tương ứng với đỉnh đầu, đỉnh cuối và trọng số của cạnh tương ứng.

	Hãy sử dụng thuật toán Prim, viết chương trình tìm cây khung nhỏ nhất của đồ thị bắt đầu tại đỉnh u=1. Cây khung nhỏ nhất tìm được ghi lại trong file caykhung.out theo khuôn dạng:
•	Dòng đầu tiên ghi lại độ dài cây khung nhỏ nhất;
•	Những dòng kế tiếp, mỗi dòng ghi lại ba số i, j, w tương ứng với đỉnh đầu, đỉnh cuối và trọng số cạnh tương ứng của cây khung.

			Ví dụ dưới đây sẽ minh họa cho file dothi.in và caykhung.out của đồ thị.
 * dothi.in
5
1	2	2
1	3	4
1	4	6
1	5	8
2	3	7
2	5	5
3	4	3
4	5	1

 * ketqua.out
10
1	2
1	3
3	4
4	5

 */

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <string.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int a[MAX][MAX];
int du[MAX], dv[MAX], de[MAX];
int chuaxet[MAX];
int M, N, socanh;
long total;

void init(){
    for(int i = 0; i<N; i++){
        chuaxet[i] = TRUE;
    }
    socanh = 0;total = 0;
}
void input(){
    FILE *fi;
    int dd, dc, dl;
    fi = fopen("dothi.in", "r");
    fscanf(fi, "%d %d\n", &N, &M);
    for(int i = 0; i<M; i++){
        fscanf(fi, "%d %d %d\n", &dd, &dc, &dl);
        a[dd-1][dc-1] = dl;
        a[dc-1][dd-1] = dl;
    }
    fclose(fi);
}
void prim(){
    int sodinh = 0;
    int ds[MAX];
    int mind, md, mj, j;
    ds[sodinh++] = 0;
    chuaxet[0] = FALSE;
    while (sodinh < N){
        mind = 32766;
        for (int i = 0; i<sodinh; i++){
            for (j=0; j<N; j++){
                if (chuaxet[j]){
                    if (a[ds[i]][j] < mind && a[ds[i]][j] > 0){
                        md = ds[i];
                        mj = j;
                        mind = a[ds[i]][j];
                    }
                }
            }
        }

        ds[sodinh++] = mj;
        total += mind;
        du[socanh] = md;
        dv[socanh] = mj;
        de[socanh++] = mind;
        chuaxet[mj] = FALSE;

    }
}
void output(){
    FILE *fo;
    fo = fopen("ketqua.out", "w");
    fprintf(fo, "%d\n", total);
    for(int i=0; i<socanh; i++){
        fprintf(fo, "%d %d\n", du[i]+1, dv[i]+1, de[i]);
    }
    
    fclose(fo);
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();
    init();
    prim();
    output();
    return (EXIT_SUCCESS);
}

